UVa/107 - The Cat in the Hat/The Cat in the Hat.htm

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
   2 <!-- saved from url=(0031)http://acm.uva.es/p/v1/107.html -->
   3 <!--Converted with LaTeX2HTML 96.1 (Feb 5, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds --><HTML><HEAD><TITLE>The Cat in the Hat</TITLE>
   4 <META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
   5 <META content="The Cat in the Hat" name=description>
   6 <META content=htmlatex name=keywords>
   7 <META content=document name=resource-type>
   8 <META content=global name=distribution><LINK
   9 href="The%20Cat%20in%20the%20Hat_archivos/htmlatex.css" rel=STYLESHEET>
  10 <META content="MSHTML 6.00.6000.16414" name=GENERATOR></HEAD>
  11 <BODY lang=EN bgColor=#ffffff>
  12 <H1><BR clear=all>
  13 <CENTER>
  14 <TABLE bgColor=#0060f0>
  15   <TBODY>
  16   <TR>
  17     <TD><B><FONT color=#c0ffff size=5>&nbsp;<A
  18       name=SECTION0001000000000000000000>The Cat in the
  19   Hat</A></FONT>&nbsp;</B></TR></TBODY></TABLE></CENTER></H1>
  20 <P>
  21 <H2><FONT color=#0070e8><A
  22 name=SECTION0001001000000000000000>Background</A></FONT></H2>
  23 <P>(An homage to Theodore Seuss Geisel)
  24 <P>The Cat in the Hat is a nasty creature,<BR>But the striped hat he is wearing
  25 has a rather nifty feature.
  26 <P>With one flick of his wrist he pops his top off.
  27 <P>Do you know what's inside that Cat's hat?<BR>A bunch of small cats, each with
  28 its own striped hat.
  29 <P>Each little cat does the same as line three,<BR>All except the littlest ones,
  30 who just say ``Why me?''
  31 <P>Because the littlest cats have to clean all the grime,<BR>And they're tired
  32 of doing it time after time!
  33 <P>
  34 <H2><FONT color=#0070e8><A name=SECTION0001002000000000000000>The
  35 Problem</A></FONT></H2>
  36 <P>A clever cat walks into a messy room which he needs to clean. Instead of
  37 doing the work alone, it decides to have its helper cats do the work. It keeps
  38 its (smaller) helper cats inside its hat. Each helper cat also has helper cats
  39 in its own hat, and so on. Eventually, the cats reach a smallest size. These
  40 smallest cats have no additional cats in their hats. These unfortunate smallest
  41 cats have to do the cleaning.
  42 <P>The number of cats inside each (non-smallest) cat's hat is a constant,
  43 <I>N</I>. The height of these cats-in-a-hat is <IMG height=31
  44 alt=tex2html_wrap_inline35 src="The%20Cat%20in%20the%20Hat_archivos/107img1.gif"
  45 width=30 align=middle> times the height of the cat whose hat they are in.
  46 <BLOCKQUOTE>The smallest cats are of height one; <BR>these are the cats that
  47   get the work done. </BLOCKQUOTE>All heights are positive integers.
  48 <P>Given the height of the initial cat and the number of worker cats (of height
  49 one), find the number of cats that are not doing any work (cats of height
  50 greater than one) and also determine the sum of all the cats' heights (the
  51 height of a stack of all cats standing one on top of another).
  52 <P>
  53 <H2><FONT color=#0070e8><A name=SECTION0001003000000000000000>The
  54 Input</A></FONT></H2>
  55 <P>The input consists of a sequence of cat-in-hat specifications. Each
  56 specification is a single line consisting of two positive integers, separated by
  57 white space. The first integer is the height of the initial cat, and the second
  58 integer is the number of worker cats.
  59 <P>A pair of 0's on a line indicates the end of input.
  60 <P>
  61 <H2><FONT color=#0070e8><A name=SECTION0001004000000000000000>The
  62 Output</A></FONT></H2>
  63 <P>For each input line (cat-in-hat specification), print the number of cats that
  64 are not working, followed by a space, followed by the height of the stack of
  65 cats. There should be one output line for each input line other than the ``0 0''
  66 that terminates input.
  67 <P>
  68 <H2><FONT color=#0070e8><A name=SECTION0001005000000000000000>Sample
  69 Input</A></FONT></H2>
  70 <P><PRE>216 125
  71 5764801 1679616
  72 0 0</PRE>
  73 <P>
  74 <H2><FONT color=#0070e8><A name=SECTION0001006000000000000000>Sample
  75 Output</A></FONT></H2>
  76 <P><PRE>31 671
  77 335923 30275911</PRE>
  78 <P></P></BODY></HTML>